BOJ_1238_파티

다익스트라(Dijkstra) 알고리즘 알고리즘 문제
가중치가 양수이며 N -> X 로 가는 최단 거리와 X -> N 으로 돌아가는 최단 거리를 구해서 더한 뒤 최댓값을 찾으면 된다

임의의 정점 N에서 X 정점으로 가는 길 : X 정점에서 이전 정점의 가중치를 더해서 탐색
X 정점에서 임의의 정점 N으로 돌아가는 길 : X 정점에서 다음 정점의 가중치를 더해서 탐색

단방향 그래프이지만 이전 정점과 다음 정점을 쉽게 탐색하기 위해 시작 노드와 끝 노드 모두에 양방향 그래프처럼 노드를 추가해주고 조건문으로 이전 탐색/다음 탐색 경우를 나눠주었다

Priority Queue에 노드를 추가할 때 가중치를 갱신해주지 않아서 헤맸다
우선순위 큐를 가중치에 따라 정렬하고 있는데, 노드의 가중치를 현재까지의 최소 비용으로 갱신해주지 않으면 미탐색 노드들이 앞으로 정렬되지 않는다!
그렇기에 다음에 방문할 노드를 결정할 수 있게 현재까지의 최단 거리를 업데이트 해야한다

더불어 이미 최단 거리가 갱신된 노드들은 우선순위 큐에 추가되지 않기 때문에 방문처리를 할 필요가 없다

package BJO;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.IntStream;

public class BJO_1238_파티 {
    // 가중치 양수
    // X부터 다른 모든 지점까지 가는데 드는 최단 비용을 구한다
    // 다익스트라 문제

    static class Node implements Comparable<Node> {
        int start;
        int end;
        int value;

        public Node(int start, int end, int value) {
            this.start = start;
            this.end = end;
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

		 
        List<Node>[] list = new ArrayList[N + 1];

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());

            list[start].add(new Node(start, end, value));
            list[end].add(new Node(start, end, value));
        }

        Queue<Node> pq = new PriorityQueue<>();
        int[] dis = new int[N + 1];
        pq.offer(new Node(X, X, 0));

        Arrays.fill(dis, 200001);
        dis[0] = 0;
        dis[X] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            for (int i = 0; i < list[node.end].size(); i++) {
                Node next = list[node.end].get(i);

                if (next.start != node.end) {
                    continue;
                }

                if (dis[next.end] > dis[node.end] + next.value) {
                    dis[next.end] = dis[node.end] + next.value;
                    pq.offer(new Node(next.start, next.end, dis[next.end]));
                }
            }
        }

        pq = new PriorityQueue<>();
        int[] disR = new int[N + 1];
        Arrays.fill(disR, 200001);
        pq.offer(new Node(X, X, 0));
        disR[0] = 0;
        disR[X] = 0;

        while (!pq.isEmpty()) {
            Node node = pq.poll();

            for (int i = 0; i < list[node.start].size(); i++) {
                Node before = list[node.start].get(i);
                if (node.start != before.end) {
                    continue;
                }

                if (disR[before.start] > disR[node.start] + before.value) {
                    disR[before.start] = disR[node.start] + before.value;
                    pq.offer(new Node(before.start, before.end, disR[before.start]));
                }
            }
        }

        IntStream.range(1, N + 1).forEach(i -> dis[i] += disR[i]);
        System.out.println(Arrays.stream(dis).max().getAsInt());
    }
}